package com.example.yangguoyou.sortapp;

import android.support.v7.app.AppCompatActivity;
import android.os.Bundle;
import android.util.Log;
import android.view.View;

import java.util.Random;

public class MainActivity extends AppCompatActivity {

    private int[] date;

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);
    }

    //由小到大排序
    public void maopaoClick(View view){
        new Thread(new Runnable() {
            @Override
            public void run() {
                int[] maopaos = genRandomArray(10000, 9999);
                StringBuffer buffer1 = new StringBuffer();
                for(int a : maopaos){
                    buffer1.append(a + ",");
                }
                Log.e("young", "start:" + buffer1.toString());

                long startTime = System.nanoTime();
                Log.e("young", "startTime:" + startTime);
                int size = maopaos.length;
                for(int i = 0; i < size - 1; i++){
                    for(int m = 0; m < size - 1 - i; m++){
                        int middle;
                        if(maopaos[m] > maopaos[m + 1]){
                            middle = maopaos[m + 1];
                            maopaos[m + 1] = maopaos[m];
                            maopaos[m] = middle;
                        }
                    }
                }
                long consumingTime = System.nanoTime() - startTime;
                Log.e("young", "endTime:" + consumingTime);
                StringBuffer buffer2 = new StringBuffer();
                for(int a : maopaos){
                    buffer2.append(a + ",");
                }
                Log.e("young", "end:" + buffer2.toString());
            }
        }).start();
    }

    //快速排序
    public void quickClick(View view){
        new Thread(new Runnable() {
            @Override
            public void run() {
                int[] quicks = genRandomArray(10000, 9999);

                StringBuffer buffer1 = new StringBuffer();
                for(int a : quicks){
                    buffer1.append(a + ",");
                }
                Log.e("young", "start:" + buffer1.toString());
                long startTime = System.nanoTime();
                Log.e("young", "startTime:" + startTime);
                quickSort(quicks, 0, quicks.length - 1);
                long consumingTime = System.nanoTime() - startTime;
                Log.e("young", "endTime:" + consumingTime);
                StringBuffer buffer2 = new StringBuffer();
                for(int a : quicks){
                    buffer2.append(a + ",");
                }
                Log.e("young", "end:" + buffer2.toString());
            }
        }).start();
    }

    public void selectClick(View view){
        new Thread(new Runnable() {
            @Override
            public void run() {
                int[] selects = genRandomArray(100, 99);
                StringBuffer buffer1 = new StringBuffer();
                for(int a : selects){
                    buffer1.append(a + ",");
                }
                Log.e("young", "start:" + buffer1.toString());
                long startTime = System.nanoTime();
                Log.e("young", "startTime:" + startTime);

                int size = selects.length;
                int temp = 0 ; //中间变量
                for(int i = 0; i < size - 1; i++){
                    int k = i;
                    for(int j = i + 1; j < size; j++){
                        if(selects[k] > selects[j]){
                            k = j;
                        }
                    }
                    temp = selects[i];
                    selects[i] = selects[k];
                    selects[k] = temp;
                }

                long consumingTime = System.nanoTime() - startTime;
                Log.e("young", "endTime:" + consumingTime);
                StringBuffer buffer2 = new StringBuffer();
                for(int a : selects){
                    buffer2.append(a + ",");
                }
                Log.e("young", "end:" + buffer2.toString());
            }
        }).start();
    }

    public void charuClick(View view){
        new Thread(new Runnable() {
            @Override
            public void run() {
                int[] inserts = genRandomArray(20, 19);
                StringBuffer buffer1 = new StringBuffer();
                for(int a : inserts){
                    buffer1.append(a + ",");
                }
                Log.e("young", "start:" + buffer1.toString());
                long startTime = System.nanoTime();
                Log.e("young", "startTime:" + startTime);

                int size = inserts.length;
                for(int i = 0; i < size; i++){
                    int temp = inserts[i];
                    int k = 0;
                    boolean boo = false;
                    for(int j = i - 1; j >= 0; j--){
                        if(temp < inserts[j]){
                            k = j;
                            inserts[j + 1] = inserts[j];
                            boo = true;
                        }else{
                            break;
                        }
                    }
                    if(boo)
                    inserts[k] = temp;
                }

                long consumingTime = System.nanoTime() - startTime;
                Log.e("young", "endTime:" + consumingTime);
                StringBuffer buffer2 = new StringBuffer();
                for(int a : inserts){
                    buffer2.append(a + ",");
                }
                Log.e("young", "end:" + buffer2.toString());
            }
        }).start();
    }

    public static void quickSort(int[] numbers,int low,int high)
    {
        if(low < high) {
            int middle = getMiddle(numbers,low,high); //将numbers数组进行一分为二
            quickSort(numbers, low, middle-1);   //对低字段表进行递归排序
            quickSort(numbers, middle+1, high); //对高字段表进行递归排序
        }

    }

    //把第一个数作为中轴，把数组小于中轴的放到中轴左边，大于中轴的放到数组右边，最后返回中轴的位置，此时数组已经根据中轴排序好。
    //然后左轴和右轴再次同样的操作。
    public static int getMiddle(int[] numbers, int low,int high)
    {
        int temp = numbers[low]; //数组的第一个作为中轴
        while(low < high){
            while(low < high && numbers[high] >= temp){
                high--;
            }
            numbers[low] = numbers[high];//比中轴小的记录移到低端 numbers[0] = numbers[1] = 1
            while(low < high && numbers[low] < temp){
                low++;
            }
            numbers[high] = numbers[low] ; //比中轴大的记录移到高端 numbers[1] = numbers[1] = 1
        }
        numbers[low] = temp ; //中轴记录到尾
        return low ; // 返回中轴的位置   以上算法好像是返回数组最小值得下标
    }



    // 从 m个整数中随机抽取 n个整数，条件: m > n
    public static int[] genRandomArray(int m , int n) {
        if(m<=0) return null;
        if(n<=0) return null;
        if(m< n) return null;

        int[] intRet = new int[n];
        int intRd = 0; // 存放随机数
        int count = 0; // 记录生成的随机数个数
        boolean flag = false;  // 是否已经生成过标志
        while(count< n){
            Random rdm = new Random(System.currentTimeMillis());
            intRd = Math.abs(rdm.nextInt())%m +1;
            for(int i=0;i<count;i++){
                if(intRet[i]==intRd){
                    flag = true;
                    break;
                }else{
                    flag = false;
                }
            }
            if(flag==false){
                intRet[count] = intRd;
                count++;
            }
        }
        return intRet;
    }

}
